Efficient for sparse graphs and neighbor queries.

  • Space: Stores vertices and edges, costing $O(n+m)$. This is highly efficient for sparse graphs where $m$ is much smaller than $n^2$.
  • Adjacency Test: To check for an edge $(u,v)$, we search $u$'s neighbor list. This takes $O(\deg(u))$ time. If using a hash set, this becomes $O(1)$ on average.
  • List Neighbors: This is the adjacency list's strength. Retrieving all of $u$'s neighbors is optimally fast, taking $O(\deg(u))$ time.
  • Add / Remove Edge: With neighbor lists stored as hash sets, adding or removing an edge is very fast, typically $O(1)$ on average.